USE Lib
GO

---------------------------------------------------------------------------
-- BEGIN MAINTENANCE WRAPPER
----------------------------
IF EXISTS (SELECT * FROM sysobjects WHERE type = 'FN' AND name = 'fn_levenshtein') BEGIN
	DROP  FUNCTION  tsql.fn_levenshtein
	PRINT '<<< DROP FUNCTION tsql.fn_levenshtein - Completed with SUCCESS >>>'
END
GO
----------------------------
-- END MAINTENANCE WRAPPER
---------------------------------------------------------------------------

SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO


/*================================================================================================
Name:			tsql.fn_levenshtein
Type:			User defined function 
Owner:			
Description:	Returns the distance between 2 strings 
Parameters:		@str_ref = reference string
				@str_cmp = compare string 
Dependens on:  	
Usage:			SELECT [tsql].[fn_levenshtein] ('Edward','Eduardo')
--------------------------------------------------------------------------------------------------
Project:		http://sqllib.codeplex.com/
Help:			http://sqllib.codeplex.com/wikipage?title=fn_levenshtein&referringTitle=Documentation		
Reference:		http://en.wikipedia.org/wiki/Levenshtein_distance
Version:		20121102
SrcCtrlApp:		SVN
SrcCtrlPath:	http://sqllib.codeplex.com/SourceControl/list/changesets
--------------------------------------------------------------------------------------------------
History:		11/02/2012 - Adrian E Dudau - Function created
================================================================================================*/
CREATE FUNCTION [tsql].[fn_levenshtein] (@str_ref NVARCHAR(MAX),@str_cmp NVARCHAR(MAX))
RETURNS BIGINT
AS

BEGIN /*FUNCTION*/

	DECLARE @len_ref INT
	DECLARE @len_cmp INT  
	DECLARE @idx_ref INT
	DECLARE @idx_cmp INT
	DECLARE @idx_tmp INT  
	DECLARE @chr_ref NCHAR(1)
	DECLARE @chr_cmp NCHAR(1)
	DECLARE @bin_ref VARBINARY(8000)
	DECLARE @bin_cmp VARBINARY(8000)  
	DECLARE @lev_dist BIGINT

	SET @len_ref = LEN(@str_ref)
	SET @idx_ref = 1
	SET @len_cmp = LEN(@str_cmp)
	SET @idx_cmp = 1
	SET @bin_cmp = 0x0000
	SET @lev_dist = 0  


	IF @str_ref = @str_cmp BEGIN 
		RETURN 0 
	END 

	WHILE @idx_cmp <= @len_cmp BEGIN   
		SET @bin_cmp = @bin_cmp + CAST(@idx_cmp AS BINARY(2))
		SET @idx_cmp = @idx_cmp + 1  
	END	     
		
	WHILE @idx_ref <= @len_ref   BEGIN    
		SET @chr_ref = SUBSTRING(@str_ref, @idx_ref, 1)
		SET @lev_dist = @idx_ref
		SET @bin_ref = CAST(@idx_ref AS BINARY(2))
		SET @idx_cmp = 1     
				
		WHILE @idx_cmp <= @len_cmp    BEGIN      
			SET @chr_cmp = SUBSTRING(@str_cmp, @idx_cmp, 1)
			SET @lev_dist = @lev_dist + 1  
			    
			SET @idx_tmp = CAST(SUBSTRING(@bin_cmp, (@idx_cmp + @idx_cmp - 1), 2) AS INT) 
					 + CASE WHEN @chr_ref = @chr_cmp THEN 0 ELSE 1 END      
			SET @lev_dist = CASE WHEN @lev_dist > @idx_tmp THEN @idx_tmp ELSE @lev_dist END      
		
			SET @idx_tmp = CAST(SUBSTRING(@bin_cmp, @idx_cmp + @idx_cmp + 1, 2) AS INT) + 1      
			SET @lev_dist = CASE WHEN @lev_dist > @idx_tmp THEN @idx_tmp ELSE @lev_dist END      		
			
			SET @bin_ref = @bin_ref + CAST(@lev_dist AS BINARY(2))
			SET @idx_cmp = @idx_cmp + 1    
		END    
				
		SET @bin_cmp = @bin_ref
		SET @idx_ref = @idx_ref + 1  
	END   

	RETURN @lev_dist
	
END /*FUNCTION*/
	
	
GO

---------------------------------------------------------------------------
-- BEGIN MAINTENANCE WRAPPER
-- Verify completion
----------------------------
IF EXISTS(SELECT * FROM sysobjects WHERE type = 'FN' AND name = 'fn_levenshtein') BEGIN 
	PRINT '<<< CREATE FUNCTION tsql.fn_levenshtein - Completed with SUCCESS >>>'
END

ELSE BEGIN 
	PRINT '<<< CREATE FUNCTION tsql.fn_levenshtein - Completed with ERROR >>>'
END

GO
----------------------------
-- END MAINTENANCE WRAPPER
---------------------------------------------------------------------------
